#include<iostream>
#include<queue>
using namespace std;
int N = 10e9;
queue<int> q[200];
void AOE(int graph[200][200], int v[200], int n)
{
	int i = 0;
	//q[i].push(0);
	for (i; i < n; i++)
	{
		int j = 0;
		for (j; j < n; j++)
		{
			if (graph[i][j] != N)
			{
				if (v[j] < v[i] + graph[i][j])
				{
					v[j] = v[i] + graph[i][j];
					while (!q[j].empty())
					{
						q[j].pop();
					}
					queue<int> qf = q[i];
					while (!qf.empty())
					{
						q[j].push(qf.front());
						qf.pop();
					}
					q[j].push(i);
					//q[j].push(j);
				}
			}
		}
	}
}
int main()
{
	int n, k;
	int graph[200][200] = { 0 };
	int v[200] = { 0 };
	cin >> n >> k;
	int i = 0;
	for (i; i < n; i++)
	{
		int j = 0;
		for (j; j < n; j++)
		{
			graph[i][j] = N;
		}
	}
	while (k--)
	{
		int m, n, w;
		cin >> m >> n >> w;
		graph[m][n] = w;
	}
	AOE(graph, v, n);
	int max = 0;
	int maxi = 0;
	int map[200][200] = { 0 };

	for (i = 0; i < n; i++)
	{
		if (v[i] > max)
		{
			max = v[i];
			maxi = i;
		}
		//cout << v[i] << ' ';
	}
	   
	for (i = 0; i <= maxi; i++)
	{
		if (i==maxi||(graph[i][maxi] != N && graph[i][maxi] + v[i] == max&&i!=q[maxi].back()))
		{
			int pre = q[i].front();
			q[i].pop();
			if (i != maxi)
				q[i].push(i);
			q[i].push(maxi);
			while (!q[i].empty())
			{
				map[pre][q[i].front()] = 1;
				//	cout << pre << ' ' << q[maxi].front() << endl;
				pre = q[i].front();
				q[i].pop();
				
			}
		}
	}
	
	cout << max << endl;

	for (i = 0; i < n; i++)
	{
		int j = 0;
		for (j; j < n; j++)
		{
			if (map[i][j] == 1)
			{
				cout << i << ' ' << j << endl;
			}
		}
		cout << endl;
	}
}